package fun.coding.jeffreys.judge;

public class LongestIncreasingSubsequence {

	public static void main(String[] args) {
		LongestIncreasingSubsequence instance = new LongestIncreasingSubsequence();
		int[] test1 = {2, 4, 1, 3}; // 2
		System.out.println(instance.longestIncreasingSubsequence(test1));
		
		int[] test2 = {1, 1, 1, 1, 1}; // 5
		System.out.println(instance.longestIncreasingSubsequence(test2)); 
		
		int[] test3 = {10, 1, 11, 2, 12, 3, 11}; // 4
		System.out.println(instance.longestIncreasingSubsequence(test3));
		
		int[] test4 = {88,4,24,82,86,1,56,74,71,9,8,18,26,53,77,87,60,27,69,17,76,23,67,14,98,13,10,83,20,43,39,29,92,31,0,30,90,70,37,59}; // 10
		System.out.println(instance.longestIncreasingSubsequence(test4));

		int[] test5 = {5, 4, 3, 2, 1}; // 1
		System.out.println(instance.longestIncreasingSubsequence(test5));
	}
	
	/**
	 * Given a sequence of integers, find the longest increasing (non-decreasing) subsequence (LIS).
		You code should return the length of the LIS.
		Example
		For [5, 4, 1, 2, 3], the LIS  is [1, 2, 3], return 3
		For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7] or [2, 4, 5, 7], but you only need to return 4
		
		http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/
	 */
    public int longestIncreasingSubsequence(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        // lookup[i] stands for the if char i is part of the LIS, what's the LIS
        // f(i) = max(f(0,i-1) + 1), or 1 if all the elements before is larger than array[i]
        int[] lookup = new int[nums.length];
        lookup[0] = 1;
        
        for (int i = 1; i < nums.length; i++) {
        	int max = 1;
        	for (int t = i - 1; t >= 0; t--) {
        		if (nums[t] <= nums[i]) {
        			max = Math.max(lookup[t] + 1, max);
        		}
        	}
        	lookup[i] = max;
        }
                
        int max = lookup[0];
        
        // pick the global largest from the result
        for (int i = 1; i < lookup.length; i++) {
        	max = Math.max(max, lookup[i]);
        }
        
        return max;
   }

}
